var arr = [3, 5, 7, 1, 4, 56, 12, 78, 25, 0, 9, 3, 8, 42, 37];

// 冒泡排序O(n*n)
// function selectionSort(arr) {
//   const len = arr.length;
//   let count = 0;
//   for (let i = 0; i < len; i++) {
//     for (let j = 0; j < len - 1 - i; j++) {
//       console.log(++count);
//       if (arr[j] > arr[j + 1]) {
//         var a = arr[j];
//         arr[j] = arr[j + 1];
//         arr[j + 1] = a;
//       }
//     }
//   }
//   return arr;
// }
// console.log(selectionSort(arr));

// // 选择算排序O(n*n)
// function selectionSort(arr) {
//   const len = arr.length;
//   let count = 0;
//   for (let i = 0; i < len; i++) {
//     for (let j = i; j < len; j++) {
//       console.log(++count);
//       if (arr[i] > arr[j]) {
//         var a = arr[i];
//         arr[i] = arr[j];
//         arr[j] = a;
//       }
//     }
//   }
//   return arr;
// }
// console.log(selectionSort(arr));

// 插入排序
// function insertionSort(arr) {
//   const { length } = arr;
//   let count = 0;
//   for (let i = 1; i < length; i++) {
//     let j = i,
//       temp = arr[i];
//     while (j > 0 && arr[j - 1] > temp) {
//       console.log(++count);
//       arr[j] = arr[j - 1];
//       j--;
//     }
//     arr[j] = temp;
//   }
//   return arr;
// }
// console.log(insertionSort(arr));

// 合并排序
// console.time('merge')
// let count = 0;
// function mergeSort(arr) {
//   let len = arr.length;
//   if (len < 2) return arr;
//   let mid = Math.floor(len / 2);
//   let left = arr.slice(0, mid);
//   let right = arr.slice(mid);

//   return merge(mergeSort(left), mergeSort(right));  // 切片，把数组切成，length为 1 的数组
// }

// /**
//  * 排序并合并两个数组
//  * 要求：两个数组内部必须是已经排好序的，如果数组中只有一个，那一定是排好的
//  */
// function merge(left, right) {
//   let result = [];

//   while (left.length > 0 && right.length > 0) {
//     // console.log(++count)
//     if (left[0] <= right[0]) {
//       result.push(left.shift());
//     } else {
//       result.push(right.shift());
//     }
//   }

//   while (left.length) result.push(left.shift());
//   while (right.length) result.push(right.shift());

//   return result;
// }

// console.log(mergeSort(arr));
// console.timeEnd('merge')

// 快排
// console.time("quick");
// function quickSork(array) {
//   return quick(array, 0, array.length - 1);
// }
// function quick(array, left, right) {
//   let index;
//   if (array.length > 1) {
//     index = partition(array, left, right);

//     if (left < index - 1) {
//       quick(array, left, index - 1);
//     }
//     if (index < right) {
//       quick(array, index, right);
//     }
//   }
//   return array;
// }
// function partition(array, left, right) {
//   const pivot = array[Math.floor((right + left) / 2)];
//   let i = left;
//   let j = right;
//   while (i <= j) {
//     while (array[i] < pivot) {
//       i++;
//     }
//     while (array[j] > pivot) {
//       j--;
//     }
//     if (i <= j) {
//       var a = array[j];
//       array[j] = array[i];
//       array[i] = a;
//       i++;
//       j--;
//     }
//   }
//   return i;
// }
// console.log(quickSork(arr));

// console.timeEnd("quick");


// 计数排序
// function countingSort(arr) {
//   let maxValue = 0;
//   for (let i of arr) {
//     if (i > maxValue) {
//       maxValue = i;
//     }
//   }
//   const maxArray = new Array(maxValue + 1);

//   for (let i of arr) {
//     if (!maxArray[i]) {
//       maxArray[i] = 0;
//     }
//     maxArray[i]++;
//   }

//   const resultArr = [];
//   maxArray.forEach((ele, i) => {
//     while (ele) {
//       resultArr.push(i);
//       ele--;
//     }
//   });
//   return resultArr;
// }
// console.log(countingSort(arr));